//---------------------------------------------------
// Purpose: Functions to generate and search arrays
// Author:  John Gauch
//---------------------------------------------------
#include <iostream>
#include <vector>
using namespace std;

//---------------------------------------------------
// Create random data
//---------------------------------------------------
void random_data(vector<int> & array)
{
   for (unsigned int i=0; i<array.size(); i++)
      array[i] = random() % 100;
}

//---------------------------------------------------
// Create sorted data
//---------------------------------------------------
void sorted_data(vector<int> & array)  
{
   array[0] = random() % 10;
   for (unsigned int i=0; i<array.size(); i++)
      array[i] = array[i-1] + random() % 10;
}

//---------------------------------------------------
// Print data
//---------------------------------------------------
void print_data(vector<int> & array)  
{
   for (unsigned int i=0; i<array.size(); i++)
      cout << array[i] << " ";
   cout << endl;
}

//---------------------------------------------------
// Linear search array and returns result
//---------------------------------------------------
int linear_search(int number, vector<int> & array)  
{
   // search for number in data array
   for (unsigned int i=0; i<array.size(); i++)
   {
     cout << "checking " << i << " " << array[i] << endl;
     if (array[i] == number)
        return i;
   }
   return -1;
}

//---------------------------------------------------
// Check if array is sorted
//---------------------------------------------------
bool is_sorted(vector<int> & array)  
{
   // check if array is in sorted order 
   bool sorted = true;
   for (unsigned int i=1; i<array.size(); i++)
   {
     if (array[i-1] > array[i])
        sorted = false;
   }
   return sorted;
}

//---------------------------------------------------
// Binary search array and returns result
//---------------------------------------------------
int binary_search(int value, vector<int> & array)
{
   // Search array using divide and conquer approach
   int min_index = 0;
   int max_index = array.size() - 1;
   int mid_index = (min_index + max_index) / 2;
   cout << "checking " << mid_index << " " << array[mid_index] << endl;
   while ((array[mid_index] != value) && (max_index >= min_index))
   {
      // Change min to search right half
      if (array[mid_index] < value)
         min_index = mid_index+1;
   
      // Change max to search left half
      else if (array[mid_index] > value)
         max_index = mid_index-1;

      // Update mid location
      mid_index = (min_index + max_index) / 2;
      cout << "checking " << mid_index << " " << array[mid_index] << endl;
   }
   
   // Return results of search
   if (array[mid_index] == value)
      return(mid_index);
   else
      return(-1);
}

//---------------------------------------------------
// Main program
//---------------------------------------------------
int main()
{
   // Create array
   int size = 0;
   cout << "Enter array size: ";
   cin >> size;
   vector<int> array(size, 0);

   // Initialize array
   random_data(array);
   print_data(array);

   // Test the is_sorted function
   if (is_sorted(array))
      cout << "The array was sorted\n";
   else
      cout << "The array was NOT sorted\n";

   // Get user input
   int number = 0;
   cout << "Enter a number: ";
   cin >> number;

   // Test the linear search function
   int index = linear_search(number, array);
   if (index >= 0)
      cout << number << " was found at location " << index << endl;
   else
      cout << number << " was not found in the array" << endl;

   // Resize the array
   cout << "Enter array size: ";
   cin >> size;
   array.resize(size);

   // Initialize array
   sorted_data(array);
   print_data(array);

   // Test the is_sorted function
   if (is_sorted(array))
      cout << "The array was sorted\n";
   else
      cout << "The array was NOT sorted\n";

   // Get user input
   cout << "Enter a number: ";
   cin >> number;

   // Test the binary search function
   index = binary_search(number, array);
   if (index >= 0)
      cout << number << " was found at location " << index << endl;
   else
      cout << number << " was not found in the array" << endl;
}